package com.lizk.path;

import com.google.common.collect.Lists;
import com.lizk.graph.weight.Edge;
import com.lizk.graph.weight.WeightGraph;

import java.util.List;

/**
 * @author lizhikui
 * @date 2020/3/1 10:29
 */
public class BellmanFord {

    Node4ShortPath[] node;

    public void bellmanFord(WeightGraph<Edge<Integer>> graph, int initNodeIndex){

        node = new Node4ShortPath[graph.size()];

        node[initNodeIndex] = new Node4ShortPath(new Edge<>(initNodeIndex,initNodeIndex,0),false,0,initNodeIndex);

        //看一下数据的例子可能更好的理解这个算法
        //9->8->7->6->5->4->3->2->1->0
        //如果上面是一张图,并且计算的是9->0的最短距离,
        //第一次外部循环的内部循环是从0开始,
        //  -因为初始点是9,所以循环中0-8都直接跳过,不会进行松弛操作,
        //  -循环到9的时候,9的下一个节点是8，并且8这个节点的前一个节点9有初始的最短距离，所以可以进行松弛操作,8也计算出了最短距离
        //  -经过一整轮的内部循环,只计算了一个节点8
        //第二次外部循环的时候,同样的道理,只计算了节点7的松弛操作
        //因为把所有的节点都连接起来,最多是节点-1的边数,所以第一层循环需要执行节点-1次
        //当第节点数次数的外层循环的时候如果还能够进行松弛操作,那么说明存在"负边环".整个图不存在最短路径.

        //外层循环循环节点-1的次数,因为最小路径的边数最多为节点数-1
        for (int i = 0; i < graph.size() - 1; i++) {
            //内部循环遍历所有的边.
            for (int j = 0; j < graph.size(); j++) {
                graph.iterator(j);
                while (graph.hasNext()){
                    Edge<Integer> tmpEdge = graph.next();
                    Node4ShortPath toNode = node[tmpEdge.getTo()];
                    Node4ShortPath fromNode = node[tmpEdge.getFrom()];
                    Integer weight = tmpEdge.getWeight();

                    if (fromNode == null)
                        return;

                    if (toNode == null){
                        toNode = new Node4ShortPath(tmpEdge,false,Integer.MAX_VALUE,tmpEdge.getTo());
                    }
                    //这里也是松弛操作
                    if (!toNode.isVisit() || fromNode.getMinDistance() + weight < toNode.getMinDistance()){
                        toNode.setMinDistance(fromNode.getMinDistance() + weight);
                        toNode.setVisit(true);
                        toNode.setEdge(tmpEdge);
                        node[tmpEdge.getTo()] = toNode;
                    }
                }
            }
        }
    }

    public void printPath(int toIndex){

        int tmpFromIndex = toIndex;

        int tmpToIndex = -1;

        List<Node4ShortPath> list = Lists.newArrayList();


        while (tmpFromIndex != tmpToIndex){
            Node4ShortPath node4ShortPath = node[tmpFromIndex];
            list.add(node4ShortPath);


            tmpFromIndex = node4ShortPath.getEdge().getFrom();
            tmpToIndex = node4ShortPath.getEdge().getTo();
        }

        List<Node4ShortPath> reverse = Lists.reverse(list);
        boolean notFirst = false;
        for (Node4ShortPath n:reverse){
            if (notFirst){
                System.out.print("->");
            }else{
                notFirst = true;
            }
            System.out.print(n.getEdge().getTo());
        }
        System.out.println();
    }
}
